package divideandconquer;

import org.junit.Test;
import sort.Example;

/**
 * @author DuJiabao
 * @create 2021-01-02 11:46
 * 归并排序
 */
public class MergeSort extends Example {
    private static Comparable[] temp;  // 借用的临时存放的数组

    public static void sort(Comparable[] array) {
        temp = new Comparable[array.length];
        mergeSort(array, 0, array.length);  // 左闭右开区间，所以不需要-1
    }

    /**
     * 左闭右开区间
     *
     * @param array
     * @param start
     * @param end
     */
    private static void mergeSort(Comparable[] array, int start, int end) {
        if (end - start <= 1) return;
        int middle = (end + start) / 2;
        mergeSort(array, start, middle); //分治
        mergeSort(array, middle, end);
        merge(array, start, middle, end); // 合并
    }

    private static void merge(Comparable[] array, int start, int middle, int end) {
        int p1 = start;
        int p2 = middle;
        for (int i = start; i < end; i++) {
            if (p1 >= middle) temp[i] = array[p2++];  // p1已经到结尾了，把剩下的p2放进去
            else if (p2 >= end) temp[i] = array[p1++]; //同上
            else if (less(array[p1], array[p2])) temp[i] = array[p1++]; // 把小的放进去
            else temp[i] = array[p2++];
        }
        for (int i = start; i < end; i++) {
            array[i] = temp[i];  // 保存回array
        }
    }

    @Test
    public void test() {
        long currentTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            Integer[] arr = new Integer[]{10, -1, 2, 11, 23, -100, 40, 20, 20, 30, 40, 10, 30, 30, 22, 30, 10, 2, 3, 2, 10, 20};
            sort(arr);
        }
        Integer[] arr = new Integer[]{10, -1, 2, 11, 23, -100, 40, 20, 20, 30, 40, 10, 30, 30, 22, 30, 10, 2, 3, 2, 10, 20};
        sort(arr);
        System.out.println("isSorted: " + isSorted(arr));
        System.out.println("Use time: " + (System.currentTimeMillis() - currentTime));
        show(arr);
    }
}
